// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

func left(i int) int {
	return 2 * i
}

func right(i int) int {
	return 2*i + 1
}

func maxHeapify(array []int, i int) []int {
	l := left(i) + 1
	r := right(i) + 1
	var largest int
	if l < len(array) && l >= 0 && array[l] > array[i] {
		largest = l
	} else {
		largest = i
	}
	if r < len(array) && r >= 0 && array[r] > array[largest] {
		largest = r
	}
	if largest != i {
		array[i], array[largest] = array[largest], array[i]
		array = maxHeapify(array, largest)
	}
	return array
}

func buildMaxHeap(array []int) []int {
	for i := len(array)/2 - 1; i >= 0; i-- {
		array = maxHeapify(array, i)
	}
	return array
}

func heapSortFunc(array []int) []int {
	array = buildMaxHeap(array)
	size := len(array)
	for i := size - 1; i >= 1; i-- {
		array[0], array[i] = array[i], array[0]
		size--
		maxHeapify(array[:size], 0)
	}
	return array
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	res := heapSortFunc(array)
	fmt.Println(res)
}

//$ go run interview6-18.go
//[7 8 18 23 28 33 56 99]
